package com.github.kezhenxu94.playground.leetcode;

/**
 * 464. Can I Win
 * 
 * In the "100 game," two players take turns adding, to a running total, any
 * integer from 1..10. The player who first causes the running total to reach or
 * exceed 100 wins.
 * 
 * What if we change the game so that players cannot re-use integers?
 * 
 * For example, two players might take turns drawing from a common pool of
 * numbers of 1..15 without replacement until they reach a total >= 100.
 * 
 * Given an integer maxChoosableInteger and another integer desiredTotal,
 * determine if the first player to move can force a win, assuming both players
 * play optimally.
 * 
 * You can always assume that maxChoosableInteger will not be larger than 20 and
 * desiredTotal will not be larger than 300.
 * 
 * Example
 * 
 * Input:
 * 
 * maxChoosableInteger = 10
 * 
 * desiredTotal = 11
 * 
 * Output:
 * 
 * false
 * 
 * Explanation: No matter which integer the first player choose, the first
 * player will lose. The first player can choose an integer from 1 up to 10. If
 * the first player choose 1, the second player can only choose integers from 2
 * up to 10. The second player will win by choosing 10 and get a total = 11,
 * which is >= desiredTotal. Same with other integers chosen by the first
 * player, the second player will always win.
 * 
 * @author kezhenxu
 *
 */
public class Solution464CanIWin {

	public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
		boolean[] chosen = new boolean[maxChoosableInteger + 1];
		int[] addCount = new int[] { 0 };
		return backtracking(maxChoosableInteger, desiredTotal, chosen, addCount);
	}

	private boolean backtracking(int maxChoosableInteger, int desiredTotal, boolean[] chosen, int[] addCount) {
		for (int i = 1; i <= maxChoosableInteger; i++) {
			if (chosen[i])
				continue;

			chosen[i] = true;
			addCount[0]++;

			if (sumUp(chosen) >= desiredTotal)
				return addCount[0] % 2 == 1;
			if (backtracking(maxChoosableInteger, desiredTotal, chosen, addCount))
				return true;

			chosen[i] = false;
			addCount[0]--;
		}
		return false;
	}

	private int sumUp(boolean[] chosen) {
		int result = 0;
		for (int i = 0; i < chosen.length; i++)
			result += chosen[i] ? 1 : 0;
		return result;
	}
}
